package leetcode_2401_2500;

public class LeeCode_2430 {
    public static void main(String[] args) {
        System.out.println(deleteString("abcabcdabc"));
        System.out.println(deleteString("aaabaab"));
        System.out.println(deleteString("aaaaa"));
    }
    private static int deleteString(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        if (all(cs)){
            return n;
        }
        int[][] lcp = new int[n + 1][n + 1];
        for(int i = n - 1; i >= 0; i--){
            for (int j = n - 1; j > i;j--){
                if (cs[i] == cs[j]){
                    lcp[i][j] = lcp[i + 1][j + 1] + 1;
                }
            }
        }
        int[] f = new int[n];
        for (int i = n - 1; i >= 0;i--){
            for(int j = 1; i + j * 2 <= n; j++){
                if (lcp[i][i + j] >= j){
                    f[i] = Math.max(f[i], f[i + j]);
                }
            }
            f[i]++;
        }
        return f[0];
    }
    private static boolean all(char[] cs){
        for (int i = 1; i < cs.length; i++) {
            if (cs[i] != cs[0]){
                return false;
            }
        }
        return true;
    }
}
